package com.changanw.code22;

import java.util.ArrayList;
import java.util.List;

/**
 * @author changanw
 * @description
 *
 *
 * 当  L > R 时可以往下走
 * 当 L < R 时 退出当前遍历
 * 当 L=R = n时 满足结果需求
 * @date 2023/7/12 22:22
 */
public class Code22 {
  public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    if (n == 0){
      return res;
    }
    dfs("",n,n,res);
    return res;

  }

  /**
   *
   * @param curStr 当前递归得到的结果
   * @param left 左括号还有几个
   * @param right 右括号还有几个
   * @param res 结果级
   */
  private void dfs(String curStr,int left,int right,List<String> res){
    //每一次尝试，都生成新的字符串变量，无需回溯
    if (left == 0 && right == 0){
      res.add(curStr);
    }
    //剪枝：左括号可以使用的个数严格大于右括号可以使用的个数，才剪枝
    if (left > right){
      return;
    }
    if (left > 0){
      dfs(curStr+"(",left - 1,right,res);
    }
    if (right > 0) {
      dfs(curStr + ")", left, right - 1, res);
    }
  }

  /**
   *
   * @param cur 当前字符串
   * @param n 总数
   * @param light 左括号个数
   * @param right 右括号个数
   * @param res 结果级
   */
  private void dfs2(String cur,int n,int light,int right,List<String> res){
    //两边括号数量都等于n时 加入结果集
    if (light == n && right == n){
      res.add(cur);
      return;
    }
    //如果发现右括号的数量大于左括号的数量，直接跳出
    if (right > light){
      return;
    }
    //添加左括号
    if (light < n){
      dfs2(cur + "(",n,light + 1,right,res);
    }
    //添加右括号
    if (right < n){
      dfs2(cur + ")",n,light,right + 1,res);
    }

  }


  public static void main(String[] args) {
    Code22 code22 = new Code22();
    List<String> strings = code22.generateParenthesis(2);
    for (String string : strings) {
      System.out.println(string);
    }
  }
}
